package com.cdream.basic.algorithm.leetcode.dp;

import cn.hutool.json.JSONUtil;

import java.util.Arrays;

/**
 * @author cdream
 * @date 6/9/21
 */
public class Question64 {
    public static void main(String[] args) {
        new Question64().minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}});
    }

    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row + 1][col + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                int add = grid[i - 1][j - 1];

                int a = dp[i - 1][j];
                int b = dp[i][j - 1];
                if (a == Integer.MAX_VALUE && b == Integer.MAX_VALUE) {
                    dp[i][j] = add;
                } else if (a == Integer.MAX_VALUE) {
                    dp[i][j] = b + add;
                } else if (b == Integer.MAX_VALUE) {
                    dp[i][j] = a + add;
                }else {
                    dp[i][j] = Math.min(a, b) + add;
                }

            }
        }
        System.out.println(JSONUtil.toJsonPrettyStr(dp));
        return dp[row][col];
    }
}
